package MultiSourceShortestPath;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class AsFarFromLandAsPossible {
    public int maxDistance(int[][] grid) {
        // 辅助向量数组
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,-1,1};

        int m = grid.length; // 对应 x 坐标
        int n = grid[0].length; // 对应 y 坐标

        // 结果数组, dp[i][j] = 其上一个节点的值 + 1, -1 表示未访问节点, 0 表示出发节点
        int[][] dp = new int[m][n];
        for(int[] row : dp) {
            Arrays.fill(row, -1);
        }

        // 用队列存储 1 节点坐标
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    // 如果存在陆地, 把陆地坐标放到队列中
                    queue.offer(new int[]{i, j});
                    dp[i][j] = 0;
                }
            }
        }

        int max = -1; // 记录某一海洋到与它最近的陆地区域的距离是最大的
        while(!queue.isEmpty()) {
            int size = queue.size(); // 所有起点同时只能走一步
            while(size-- != 0) {
                // 取出点
                int[] point = queue.poll();
                // 分解点坐标
                int Ox = point[0];
                int Oy = point[1];

                // 起点向前走一步
                for(int i = 0; i < 4; i++) {
                    int x = Ox + dx[i];
                    int y = Oy + dy[i];

                    if(x >= 0 && x < m && y >= 0 && y < n && dp[x][y] == -1) {
                        queue.offer(new int[]{x, y});
                        dp[x][y] = dp[Ox][Oy] + 1;
                        if(dp[x][y] > max) {
                            max = dp[x][y];
                        }
                    }
                }
            }
        }
        return max;
    }
}
